package graphPath;



import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

import org.jgrapht.WeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class ReadWeightedGraph {
	


		public static WeightedGraph <String, DefaultWeightedEdge> readInGraph(String fileName){
			WeightedGraph <String, DefaultWeightedEdge> graph = new 
					SimpleWeightedGraph <String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
			
			Scanner read = null;
			int vexNum = 0;
			double weight =0;
			
			try{
				read = new Scanner(new File(fileName));
			} catch(FileNotFoundException e){
				e.printStackTrace();
			}
			
			if(read.hasNextInt()){
				vexNum = read.nextInt();
			}
			
//			if(read.hasNextDouble()){
//				weight = read.nextDouble();
//			}
			
			read.nextLine();
			
			//Add vertex to the graph
			for(int i = 0; i < vexNum; i++){
				String v = String.valueOf(i);
				graph.addVertex(v);
			}
			
			
			String line;
			String[] lineToken;
			while(read.hasNextLine()){
				line = read.nextLine();
				lineToken = line.split(" ");
				
								
//				int size = lineToken.length;
				String v1 = lineToken[0];
				String v2 = lineToken[1];
				DefaultWeightedEdge e1 = graph.addEdge(v1, v2);
				String w = lineToken[2];
				graph.setEdgeWeight(e1, Double.valueOf(w));
				
//				String v2;
//				for(int i = 1; i < size; i++){
//					v2 = " " + lineToken[i];
//					graph.addEdge(v1, v2);
//				}
			}
			read.close();
			
			
			return graph;
		}
		/**
		 * @param args
		 */
		

	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	
		
		WeightedGraph <String, DefaultWeightedEdge> graph = readInGraph("graph_zhu_input_001.txt");
		
//		System.out.println(graph);
		
//		for(DefaultWeightedEdge edge : graph.edgeSet()){
//			System.out.println(graph.getEdgeWeight(edge));
//	}
		
		
		
		 DeepFirstSearch dfs = new DeepFirstSearch();
		 dfs.initial(graph);
		 
		 List<Map.Entry<Integer,Integer>> list = new ArrayList<Map.Entry<Integer,Integer>>(dfs.vertex_discover.entrySet());
	     Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
	          public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
	               return o1.getValue().compareTo(o2.getValue());
	          }
	     });
		 
		System.out.print("Depth First Search Traversal: [");
		for(Map.Entry<Integer, Integer> map: list){
			System.out.print(map.getKey()+ " ");
		}
		System.out.println("]");
//		 
		 BreadthFirstSearch bfs = new BreadthFirstSearch();
		 bfs.initial(graph);
		System.out.println();
		 MinimumSpanningTree mst = new MinimumSpanningTree();
		
		 mst.mst(graph);
		 mst.getTotal();
		 
		 System.out.println();
		 System.out.println("Shortest Paths:");
		DijkstraPath test = new DijkstraPath();
		
		for(String element: graph.vertexSet()){
			test.dijkstra(graph, element);
			
		}
		

		
	}

}
